This invention relates to coding of data and is applicable to communication of data, networking, fault-tolerant computing, magnetic as well as optical recording of data.
A binary constant weight block code is a code where each member of the code, i.e., each n-bit codeword has a constant number, w, of 1's. In an effort to devise an effective and fast method for encoding and decoding constant weight codes, the inventors herein disclosed in the aforementioned '550 patent application a method of wide applicability. The advance disclosed in the '550 patent application employs a piecewise linear algorithm, P, that maps w-dimensional information vectors into code vectors, followed by the construction of binary code vectors of weight w from the code vectors. To reverse the operation, constant weight codewords are converted to w-dimensional code vectors, and a reverse piecewise linear algorithm P′ is used to map the code vectors into information vectors, from which data is recovered.
More specifically, as illustrated in FIG. 1, input data is mapped in element 2 into the w-dimensional information vectors that are subsumed by a w-dimensional parallelopiped, with possibly different size of the parallelopiped along each of the w coordinates and in which the symbols along each of the coordinate axes are spaced equally apart. The w-dimensional parallelopiped (“brick”), as illustrated in FIG. 1 by the 2-dimensional “brick” composed of elements 12 and 13′ in the plot pointing to the signal line between elements 2 and 4. The P mapping, executed in element 4, maps the w-dimensional symbols to code vectors in a w-dimensional orthoscheme, illustrated by elements 12 and 13 in the plot pointing to the signal line between elements 4 and 6. The key attribute of this mapping is that points subsumed by the orthoscheme are characterized by the fact that x1<x2<x3< . . . <xw≦n, where xi is the ith coordinate of the orthoscheme and n is the block length of the code. The code vectors developed by element 4 are applied to element 6, where the constant weight codes are developed by a mapping Γ. The mapping Γ is quite simple because the values of the coordinates can be viewed as representing the positions of the 1's in the constant weight code.
It is to be noted that the algorithm P(is obtained through a process of dissecting two polytopes of different shapes into an equal number of pieces, in such a way that corresponding pieces are congruent. In other words, the algorithm is a description of the transformations required to dissect the first polytope and to reassemble the pieces so as to form the second polytope. Because of the specific dissections used, this same algorithm also maps vectors with integer coordinates inside the first polytope to vectors with integer coordinates in the second polytope. Furthermore, this algorithm is piecewise affine.
One interesting application for constant weight codes involves superimposing a slow channel over a fast channel (e.g., a control channel over a data channel). Information on the fast channel can be sent using codewords from different constant weight codebooks, and the codebook that is employed is chosen by the information of the slow channel. For example, a 256 bit long codeword of constant weight 127 (codebook A) can be used to send data from the fast channel when the slow channel wishes to communicate a “0,” and a 256 bit long codeword of constant weight 129 (codebook B) can be used to send data from the fast channel when the slow channel wishes to communicate a “1.” It may be noted in passing that a 256 bit long code word of constant weight 127 can communicate a number of symbols equal to the number of ways that 127 bits can be chosen within 256 bits, and thus can be used for communicating a maximum of 251 bits
      (          251      <                        log          2                ⁡                  (                                                    256                                                                    127                                              )                    <      252        )    .
The method disclosed in the '550 application is very simple and effective, but it is characterized by an encoding/decoding processing time on the order of w2, which in applications where w is large, can become an issue.